\section{Variation on classical ruin problem}

In this problem $\tbrack{X_i}$ is an i.i.d. sequence of $\textrm{N}\paren{1,\sigma^2}$ normal random variables and $S_k = \sum_{j=1}^k X_j$. The probability of ruin is time-dependent and is interpreted as
\begin{align}
\psi\paren{u} := P\paren{S_k < -uf\paren{u,k}\vertt \textrm{ some } k\in\mathbb{Z}},
\end{align}
where
\begin{align}
f\paren{u,k} := 1 + \paren{\frac{k}{u}}^2.
\end{align}

\noindent
Then $\psi\paren{u}\rightarrow 0$ as $u\rightarrow\infty$ and the objective is to estimate this probability numerically for fixed large u.\\

\noindent
In the following let $\mathbf{S}_k := \paren{k,S_k}$ and $A=\tbrack{\paren{t,y}\vertt y < -\paren{1+t^2}}$ and assume $u>0$. The latter assumption is reasonable since we are seeking to estimate the probability that the capitalization of an insurance company, say, falls below the level $-uf(u,k)$. 

\subsection{Alternate formulation of $\psi\paren{u}$}
We prove that
\begin{align}
\psi\paren{u} = P\paren{\mathbf{S}_k\in uA\vertt \textrm{ some }k\in\mathbb{Z}_+}.
\end{align}
Let $k$ be such that $S_k<-uf\paren{u,k}$. Since $u>0$ it follows that
\begin{align*}
\frac{S_k}{u} <-\paren{1+\paren{\frac{k}{u}}^2}
\end{align*} 
and thus that $\paren{\frac{k}{u},\frac{S_k}{u}}\in A$. Hence $\mathbf{S}_k = \paren{k,S_k}\in uA$. Conversely, if $\mathbf{S}_k = \paren{k,S_k}\in uA$ then $\paren{k,S_k} = u\paren{t,y}$ for some $\paren{t,y}\in A$. Thus $\paren{\frac{k}{u},\frac{S_k}{u}}\in A$ and hence $\frac{S_k}{u} < -\paren{1+\paren{\frac{k}{u}}^2}$ which implies that $S_k < -u\paren{1+\paren{\frac{k}{u}}^2}$ since $u>0$.

\subsection{Shifting the measure}
We let $\Lambda\paren{\alpha} = \log\mathbf{E}\brackk{e^{\langle\alpha,\mathbf{S}_1\rangle}} = \log \kappa_{\mathbf{S}_1}\paren{\alpha}$, $\alpha\in\mathbb{R}^2$ and compute
\begin{align}
\widetilde{I} := \sup\tbrack{\langle\alpha,x\rangle\vertt \Lambda\paren{\alpha} = 0}.
\end{align}
First we note that 
\begin{align}
\Lambda\paren{\alpha} = \alpha_1 + \alpha_2 + \frac{1}{2}\sigma^2\alpha_2^2.
\end{align}
where $\alpha = \paren{\alpha_1,\alpha_2}$. Hence $\Lambda\paren{\alpha} = 0$ if and only if $\alpha_1 = -\alpha_2\paren{1+\frac{1}{2}\sigma^2\alpha_2}$. Thus we have
\begin{align}
\widetilde{I}\paren{x} &= \sup\tbrack{\alpha_1 x_1 + \alpha_2 x_2\vertt \alpha_1 = -\alpha_2\paren{1+\frac{1}{2}\sigma^2\alpha_2}} = \sup\tbrack{-\frac{1}{2}\sigma^2 x_1\alpha_2^2 + \paren{x_2-x_1}\alpha_2\vertt\alpha_2\in\mathbb{R}}\nonumber\\
&=\frac{1}{2}\frac{\paren{x_2-x_1}^2}{\sigma^2 x_1}.
\end{align}
for $x_1>0$.\newline

\noindent
Next we minimize $\widetilde{I}\paren{x}$ on $\partial A = \tbrack{\paren{t,y}\vertt y = -\paren{1+t^2}}$.
First note that $\widetilde{I}\vertt_{\partial A}$ is given by
\begin{align}
\widetilde{I}\paren{t,y}\vertt_{\partial A} = \frac{1}{2}\frac{\paren{t^2+t+	1}^2}{\sigma^2 t}.
\end{align}
Hence to minimize $\widetilde{I}\vertt_{\partial A}$ we solve the following equation
\begin{align}
\frac{\partial}{\partial t}\widetilde{I}\paren{t}\vertt_{\partial A} = \frac{1}{2}\frac{2\paren{t^2+t+1}\paren{2t+1}\sigma^2 t-\paren{t^2+t+1}^2\sigma^2}{\sigma^4 t^2} = 0
\end{align}
which is zero for $t \in \tbrack{\frac{1}{6}\paren{-1-\sqrt{13}},\frac{1}{6}\paren{\sqrt{13}-1}}$, where we can disregard the first solution because it is negative.\newline

\noindent
Thus on the boundary of $A$, $\widetilde{I}$ is minimized at the point 
\begin{align}
x_0 = \paren{\frac{1}{6}\paren{\sqrt{13}-1},-1-\frac{1}{36}\paren{\sqrt{13}-1}^2}.
\end{align}

\subsection{Selection of shift parameter}\label{sec:shiftParam}
We now select a vector $\alpha_0\in\mathbb{R}^2$ such that $\Lambda\paren{\alpha_0} = 0$ and $\nabla\Lambda\paren{\alpha_0} = \rho x_0$.
Under the assumption that $\Lambda\paren{\alpha_0} = 0$ we solve the following equation
\begin{align}
\nabla\Lambda\paren{\alpha} = \paren{1, 1+\sigma^2\alpha_2} = \rho\paren{\frac{1}{6}\paren{\sqrt{13}-1},-1-\frac{1}{36}\paren{\sqrt{13}-1}^2}.
\end{align}
This yields that
\begin{align}
\alpha_{0,1} & = \frac{\frac{1}{6}\paren{\sqrt{13}-1}^2+\sqrt{13}+5}{\sigma^2\paren{\sqrt{13}-1}}\paren{1+\frac{1}{2}\frac{\frac{1}{6}\paren{\sqrt{13}-1}^2+\sqrt{13}+5}{\sqrt{13}-1}}\approx 10.72\sigma^{-2},\nonumber\\
\alpha_{0,2} & = -\frac{\frac{1}{6}\paren{\sqrt{13}-1}^2+\sqrt{13}+5}{\sigma^2\paren{\sqrt{13}-1}}\approx -3.74\sigma^{-2}.\nonumber
\end{align}

\subsection{Estimating probability of ruin}
In this section we seek to estimate the probability of default with the parameters $u=100$ and $\sigma^2 = 2$. In order to visualize the problem we have drawn the ruin boundary, marked the point $100x_0$ and added 100 simulated paths under the true measure. This visualization can be seen in figure~\vref{fig:ruin}, and it is obvious that ruin in this setup will be a rare event. For these values of $u$ and $\sigma$ the exponential shift is given as
\begin{figure}
\centering
\includegraphics[width=10cm]{problem2_1.eps}
\caption{Variation on ruin problem: The ruin boundary with the point $100x_0$ marked and 100 simulated paths under the true measure.}
\label{fig:ruin}
\end{figure}
\begin{align}
\alpha_{0} & =\paren{5.36,-1.87}.\nonumber
\end{align}
Since we are seeking to estimate the probability that $S_k\leq -uf(u,k)$, we are interested in performing a change of measure for the $X_i$'s, and from the calculations above it is given that $\alpha_{0,2}$ is the optimal shift parameter. Let $\nu_0(dx)$ be the true measure of the $X_i$'s. Then the measure under which we seek to simulate the $X_i$'s is given by
\begin{align}\label{eq:shiftX}
\nu_{\alpha_2}(dx) &= \frac{e^{\alpha_2 x}}{\kappa(\alpha_2)}\nu_0(dx)\nonumber\\
  &=\frac{e^{\alpha_2 x}}{e^{\alpha_2+\frac{1}{2}\sigma^2\alpha_2^2}}f(x)dx\nonumber\\
  &=\frac{e^{\alpha_2 x}}{e^{\alpha_2+\frac{1}{2}\sigma^2\alpha_2^2}}\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(x-1)^2}{2\sigma^2}}dx	\nonumber\\
  &=\frac{1}{\sigma\sqrt{2\pi}}e^{\tfrac{-x^2+(2+2\alpha_2\sigma^2)x-(1+2\alpha_2\sigma^2+\alpha_2^2\sigma^4)}{2\sigma^2}}dx\nonumber \\
  &=\frac{1}{\sigma\sqrt{2\pi}}e^{-\tfrac{(x-(1+\alpha_2\sigma^2))^2}{2\sigma^2}}dx
\end{align}
which is recognized as the density for the N($1+\alpha_2\sigma^2$,$\sigma^2$) distribution. In order to visualize that this measure is reasonable we have made the visualization in figure~\vref{fig:ruin2}. Here we have again drawn the boundary line and this time added 100 simulated paths under the shifted measure. This shows that ruin is not a rare event under the shifted measure.\\ 
\begin{figure}
\centering
\includegraphics[width=10cm]{problem2_2.eps}
\caption{Variation on ruin problem: The ruin boundary and 100 simulated paths under the shifted measure.}
\label{fig:ruin2}
\end{figure}

\noindent
In order to estimate the probability of ruin we simulate $\mathbf{S}_k$ by simulating the $S_k$, under the measure given in equation~\eqref{eq:shiftX}. If we let $\nu_0^{\mathbf{S}_1}(d\mathbf{s})$ denote the true measure of $\mathbf{S}_1$, then the measure under which we simulate the probability of ruin is given by
\begin{align*}
\nu_{\alpha_0}^{\mathbf{S}_1}(d\mathbf{s}) &= \frac{e^{\langle \alpha_0,\mathbf{S}_1 \rangle}}{\kappa_{\mathbf{S}_1}(\alpha_0)}\nu_0^{\mathbf{S}_1}(d\mathbf{s})\\
\end{align*}
and further we have 
\begin{align*}
\nu_{\alpha_0}^{\mathbf{S}_k}(d\mathbf{s}) &= \frac{e^{\langle \alpha_0,\mathbf{S}_1 \rangle}}{\kappa_{\mathbf{S}_1}^k(\alpha_0)}\nu_0^{\mathbf{S}_1}(d\mathbf{s}).\\
\end{align*}
Thus, if we let 
\begin{align*}
Z_{\alpha} &= 1_{uA}(\mathbf{S}_k) \kappa (\alpha)^ke^{-\langle \alpha, \mathbf{S}_k\rangle}
\end{align*}
then
$$
P(\mathbf{S}_k \in uA) = E_{\nu_{\alpha_0}}\brackk{Z_{\alpha_0}}.
$$
In algorithm~\ref{Problem2Algo} we present pseudocode for simulating the probability of ruin.\newline
\begin{algorithm}
\caption{Estimation of $P\{\mathbf{S}_k \in A\}$ by importance sampling}
\label{Problem2Algo}
\begin{algorithmic}[1]
  \REQUIRE Shift parameter $\alpha = (\alpha_1,\alpha_2)$, ruin level $u$, number of paths, $N$, to generate, number of timesteps, $k$, to evaluate.
  \ENSURE  An estimate of the probability of ruin.
  \STATE $z \leftarrow 0$
  \FOR{$n \leftarrow 1$ to $N$}
  	\STATE $S_0 \leftarrow 0$
	  \FOR{$i \leftarrow 1$ to $k$}
	  	\STATE Generate $X\sim N(1+\sigma^2\alpha_2, \sigma^2)$
	  	\STATE $S_i \leftarrow S_{i-1} + X$
		\ENDFOR
	\STATE $T_u \leftarrow \inf_{j\in\mathbb{N}}\{j\vert S_j < -uf(u,j)\}$
	\STATE $z \leftarrow z + \kappa(\alpha)^{T_u}e^{-\langle \alpha, S_{T_u}\rangle} $
  \ENDFOR
  \RETURN $\frac{z}{N}$
\end{algorithmic}
\end{algorithm}

\noindent
Using the implementation of the algorithm given in appendix \ref{code2}, with the parameters found in section~\vref{sec:shiftParam}, yielded the following estimate
\begin{align}
\mathbf P \{S_k < -100 * f(100,k), \textrm{ some } k\in\mathbb{Z}_{+}\} &= 2.43*10^{-67} \pm 1.96*10^{-68}.\nonumber
\end{align}
Note that the error of our estimate, $\sigma_{Z_\alpha,u} = 1.96*10^{-68}$, is approximately an order of magnitude smaller than the estimated probability of ruin, $\mathbf P \{S_k < -100 * f(100,k), \textrm{ some } k\in\mathbb{Z}_{+}\} = 2.43*10^{-67}$. This gives us some confidence in the application of importance sampling in this scenario.
By comparison estimating the same probability using a crude Monte Carlo scheme yields an estimate of zero for the same probability, which is not unreasonable since the event is extremely rare. Code for the crude Monte Carlo simulation is included, but we have not presented pseudocode since it is straightforward.
\newpage